package leecode

func longestWPI(hours []int) (result int) {
	for i := 0; i < len(hours); i++ {
		if hours[i] > 8 {
			hours[i] = 1
		} else {
			hours[i] = -1
		}
	}
	prefix := make([]int, len(hours)+1)
	hashMap := make(map[int]int) //key 为前缀和 , value为前缀和出现的位置
	//求前缀和
	for i := 0; i < len(hours); i++ {
		prefix[i+1] = prefix[i] + hours[i]
	}
	// 子数组和>= 1
	for i := 0; i < len(prefix); i++ {
		//前缀和大于0, 说明此段时间是符合要求的
		if prefix[i] > 0 {
			result = i
		} else {
			//key如果存在就不能覆盖了
			if _, ok := hashMap[prefix[i]]; !ok {
				hashMap[prefix[i]] = i
			}
			//查找区间和为prefix[i]-1的子数组
			if index, ok := hashMap[prefix[i]-1]; ok {
				result = max(result, i-index)
			}
		}
	}
	return
}
